
#if 1

#include <iostream>

using namespace std;

//找出三个单身狗中的任何一个，也就是说一个数组中还有三个单身狗，最小的时间复杂度

/**
    这个时候由于单身狗不唯一，所以不能简单使用异或操作了。

    想法：
        对这个数组分组，分成两组，将三个单身狗，其中两个分到第一个分组，还有一个分到第二个分组。
        这个时候，对第二个分组使用异或就可以了。题目要求是任意一个。



    转化为如何分组：
        通过二进制的方式分组，首先判断每个数二进制的最后一位，0的一组，1的一组
        当然会出现三个在同一个组里的情况，这个时候判断倒数第二位，以此类推。

        这种方式总可以分成两组，并且，根据计算机的情况，最多比较32次就行了。int类型数字就4B

    注意：
        1. 如果分组导致三个都在一个组里，那么另一个组异或结果为0。
        2. 如果分组一个在第一分组，两个在第二分组，那么第二个分组一定是偶数个，也就是说分组长度为偶数的一定是两个单身狗

*/

#define BITNUM 32  //最多比较32次

int getSingleDog(int * arr,int length)
{
    //最多循环32次
    for(int i = 0;i<BITNUM;i++)
    {
        int arr_1=0,arr_2=0; //组1和组2异或的结果
        int count_1=0,count_2=0; //组1和组2的数字个数
        int mask = 1<<i; //分组掩码

        for(int j =0;j<length;j++)
        {
            if(arr[j]&1)
            {
                arr_1^=arr[j];
                count_1++;
            }else
            {
                arr_2^=arr[j];
                count_2++;
            }

            //偶数&1=0，奇数&1=1,条件是，个数为奇数，并且分组的异或结果不能为0
            if((count_1&1)&&(arr_1!=0))
            {
                return arr_1;
            }
            if((count_2&1)&&(arr_2!=0))
            {
                return arr_2;
            }

        }
    }
}
int main()
{
    cout<<"输入11个数的数组，空格隔开"<<endl;
    int arr[11];
    for(int i =0;i<11;i++)
    {

        cin>>arr[i];
    }

    cout<<"单身狗："<<getSingleDog(arr,11)<<endl;
	system("pause");
	return 0;
}
#endif
